1726D - Edge Split - CodeForces Solution

import sys
input = sys.stdin.buffer.readline 


def find_root(root_dict, x):
    L = []
    while x != root_dict[x]:
        L.append(x)
        x = root_dict[x]
    for y in L:
        root_dict[y] = x
    return x

def process(n, G):
    m = len(G)
    answer = [None for i in range(m)]
    root_dict = [i for i in range(n+1)]
    good_edges = []
    bad_edges = []
    for i in range(m):
        u, v = G[i]
        u1 = find_root(root_dict, u)
        v1 = find_root(root_dict, v)
        if u1 != v1:
            good_edges.append([u, v, i])
            root_dict[u1] = v1
            answer[i] = '0'
        else:
            bad_edges.append([u, v, i])
            answer[i] = '1'
    if len(bad_edges)==3:
        u1, v1, i1 = bad_edges[0]
        u2, v2, i2 = bad_edges[1]
        u3, v3, i3 = bad_edges[2]
        L = [u1, v1, u2, v2, u3, v3]
        L = sorted(L)
        if L[0]==L[1] and L[2]==L[3] and L[4]==L[5]:
            answer[i3] = '0'
            root_dict = [i for i in range(n+1)]
            root_dict[u3] = v3
            for u, v, i in good_edges:
                u1 = find_root(root_dict, u)
                v1 = find_root(root_dict, v)
                if u1==v1:
                    answer[i] = '1'
                    break
                else:
                    root_dict[u1] = v1
    answer = ''.join(answer)
    sys.stdout.write(f'{answer}\n')
    return

t = int(input())
for i in range(t):
    n, m = [int(x) for x in input().split()]
    G = []
    for j in range(m):
        u, v = [int(x) for x in input().split()]
        G.append([u, v])
    process(n, G)